package com.cuz.daileetcode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Day36 {

    /***
     * 一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的 金条，不管切成长度多大的两半，都要花费20个铜板。一群人想整分整块金 条，怎么分最省铜板？
     *
     * 例如,给定数组{10,20,30}，代表整块金条长度为10+20+30=60. 金条要分成10,20,30三个部分。
     * 如果， 先把长度60的金条分成10和50，花费60 再把长度50的金条分成20和30，花费50 一共花费110铜板。但是如果， 先把长度60的金条分成30和30，花费60 再把长度30金条分成10和20，花费30 一共花费90铜板。
     *
     * @param arr
     * @return
     */
    public static int lessMoney(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int res = 0;
        int cur;
        for (int j : arr) {
            pq.add(j);
        }
        while (pq.size() > 1) {
            //当前 花费 拿到两个最小的金条
            cur = pq.poll() + pq.poll();
            //累加消费
            res += cur;
            //把当前消费假如进去
            pq.add(cur);
        }
        return res;
    }


    /**
     * 贪心算法求做项目最大利润问题
     *
     * @param k       最多能做的项目数量
     * @param w       启动资金
     * @param profits 每个项目的利润
     * @param capitals 每个项目的成本
     * @return: int
     */
    public static int findMaximizedCapital(final int k, int w, final int[] profits, final int[] capitals) {
        class Node{
            int oneProfit;
            int oneCapital;

            public Node(int profit, int capital) {
                this.oneProfit = profit;
                this.oneCapital = capital;
            }

            public int getOneProfit() {
                return oneProfit;
            }

            public int getOneCapital() {
                return oneCapital;
            }
        }
        // 小根堆，按照每个项目的最小花费（成本）构建成小根堆
        final PriorityQueue<Node> minCostQueue = new PriorityQueue<Node>(Comparator.comparing(Node::getOneCapital));
        // 大根堆，按照每个项目的利润构建成一个大根堆
        final PriorityQueue<Node> maxProfitQueue = new PriorityQueue<Node>(Comparator.comparing(Node::getOneProfit).reversed());

        // 先将每个项目的成本和利润组织为一个个的节点并放入到小根堆中
        for (int i = 0; i < profits.length; i++) {
            minCostQueue.add(new Node(profits[i], capitals[i]));
        }
        // 开始做项目，每次循环代表做一个项目
        for (int i = 0; i < k; i++) {
            // 取出我当前启动资金能做的所有项目(即：项目成本小于我的启动资金的项目)，放入到大根堆中
            // 注意这里peek和poll的区别，peek 不会删除元素，poll 会删除元素
            while (!minCostQueue.isEmpty() && minCostQueue.peek().getOneCapital() <= w) {
                maxProfitQueue.add(minCostQueue.poll());
            }
            // 这里需要特别注意，很容易被忽视掉
            // 如果 maxProfitQueue 为空，则表示按照当前的启动资金，已经没有办法从小根堆（minCostQueue）里取出任何一个项目来做了
            if (maxProfitQueue.isEmpty()) {
                return w;
            }
            // 每次挑一个项目成本在我启动范围之内，并且利润最大的项目做
            final Node project = maxProfitQueue.poll();
            // 每个项目做完后，启动资金增加
            w = w + project.oneProfit;
        }

        return w;
    }

    /***
     * 给一个整数流，可以在流到任意一个整数是取出已有数据的中位数。
     *
     * 思路 设置一个大根堆和一个小根堆。依次读取整数流，若当前整数的值小于大根堆的根节点，
     * 则将其加入大根堆；反之，加入小根堆。当两个堆之间的数据数量差了两个
     * （以及上，但因为是依次的，所以两个时就会进行接下来的操作）时，
     * 例如，大根堆中有4个数，而小根堆中有2个数，则将大根堆的根节点移到小根堆中，
     * 这样大根堆中的数据个数为2，小根堆中也为2，继续流入剩余整数。在每次进行堆操作时，
     * 要保证堆成立，即每次都要检查变换后位置的数据应该放在哪里。
     * 中位数则介于大根堆和小根堆的根节点之间。其中大根堆中存放的数据都小于中位数，
     * 而小根堆中的数据都大于中位数。
     */
    public static class MidNum{
        private int count = 0;
        private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.comparing(Integer::intValue).reversed());

        //读入字符，放到合适位置
        public void insert(Integer num) {
            if (count %2 == 0) {
                maxHeap.offer(num);
                int filteredMaxNum = maxHeap.poll();
                minHeap.offer(filteredMaxNum);
            } else {
                minHeap.offer(num);
                int filteredMinNum = minHeap.poll();
                maxHeap.offer(filteredMinNum);
            }
            count++;
        }

        //求中位数
        public Double getMedian() {
            if (minHeap.size()<=0||maxHeap.size()<=0){
                throw new RuntimeException();
            }
            if (count %2 == 0) {
                return (double) (minHeap.peek() + maxHeap.peek()) / 2;
            } else {
                return new Double(minHeap.peek());
            }
        }
    }
}
